{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Score After Flipping Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matrixScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转矩阵后的得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的二元矩阵 <code>grid</code> ，矩阵中每个元素的值为 <code>0</code> 或 <code>1</code> 。</p>\n",
    "\n",
    "<p>一次 <strong>移动</strong> 是指选择任一行或列，并转换该行或列中的每一个值：将所有 <code>0</code> 都更改为 <code>1</code>，将所有 <code>1</code> 都更改为 <code>0</code>。</p>\n",
    "\n",
    "<p>在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的 <strong>得分</strong> 就是这些数字的总和。</p>\n",
    "\n",
    "<p>在执行任意次 <strong>移动</strong> 后（含 0 次），返回可能的最高分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-toogle1.jpg\" style=\"width: 500px; height: 299px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]\n",
    "<strong>输出：</strong>39\n",
    "<strong>解释：</strong>0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 20</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [score-after-flipping-matrix](https://leetcode.cn/problems/score-after-flipping-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [score-after-flipping-matrix](https://leetcode.cn/problems/score-after-flipping-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1,1],[1,0,1,0],[1,1,0,0]]', '[[0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def toggleRow(self, A: List[List[int]], r: int) -> None:\n",
    "        for c in range(len(A[r])):\n",
    "            A[r][c] = 1 - A[r][c]\n",
    "    \n",
    "    def toggleColumn(self, A: List[List[int]], c: int) -> None:\n",
    "        for r in range(len(A)):\n",
    "            A[r][c] = 1 - A[r][c]\n",
    "    \n",
    "    def rowSum(self, A: List[List[int]]) -> int:\n",
    "        return sum(\n",
    "            int(\"\".join(map(str, row)), 2)\n",
    "            for row in A\n",
    "        )\n",
    "    \n",
    "    def matrixScore(self, A: List[List[int]]) -> int:\n",
    "        for r in range(len(A)):\n",
    "            if A[r][0] == 0:\n",
    "                self.toggleRow(A, r)\n",
    "                \n",
    "        for c in range(1, len(A[0])):\n",
    "            n_ones: int = sum(A[r][c] for r in range(len(A)))\n",
    "            n_zeros: int = len(A) - n_ones\n",
    "            if n_zeros > n_ones:\n",
    "                self.toggleColumn(A, c)\n",
    "\n",
    "        return self.rowSum(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        for j in range(n):\n",
    "            if sum([grid[k][j] for k in range(m)])<=len(grid)//2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        for i in range(m):\n",
    "            t=1\n",
    "            for j in range(n-1,-1,-1):\n",
    "                result+=grid[i][j]*t\n",
    "                t*=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, A: List[List[int]]) -> int:\n",
    "        # 行变换\n",
    "        for i in range(len(A)):\n",
    "            if A[i][0]==0:\n",
    "                A[i] = [1-tmp for tmp in A[i]]\n",
    "        # 列变换\n",
    "        for j in range(1, len(A[0])):\n",
    "            cnt1 = sum(A[i][j] for i in range(len(A)))\n",
    "            if cnt1 < len(A)/2:\n",
    "                for i in range(len(A)):\n",
    "                    A[i][j] = 0 if A[i][j] else 1\n",
    "        res=0\n",
    "        for i in range(len(A)):\n",
    "            t = A[i][::-1]\n",
    "            item = [val * 2 ** inx for inx, val in zip(range(len(t)), t)]\n",
    "            res = res + sum(item)\n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        ans = m * (1 << (n-1))\n",
    "\n",
    "        for j in range(1, n):\n",
    "            cntone = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0] == 1:\n",
    "                    cntone += grid[i][j]\n",
    "                else:\n",
    "                    cntone += (1 - grid[i][j])\n",
    "            k = max(cntone, m - cntone)\n",
    "            ans += k * (1 << (n - j - 1))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        temp=2**(n-1)\n",
    "        for j in range(n):\n",
    "            Sum=sum([grid[k][j] for k in range(m)])\n",
    "            if Sum<=m//2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "                Sum=m-Sum\n",
    "            result+=Sum*temp\n",
    "            temp//=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for row in grid:\n",
    "            if row[0] == 0:\n",
    "                for j in range(n):\n",
    "                    row[j] = 1 - row[j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            num = 0\n",
    "            j = n - 1\n",
    "            while j >= 0:\n",
    "                if grid[i][n - 1 - j]:\n",
    "                    num |= 1 << j\n",
    "                j -= 1\n",
    "            ans += num\n",
    "\n",
    "        j = n - 1\n",
    "        diff = 0\n",
    "        for col in zip(*grid):\n",
    "            zero_cnt = sum(x == 0 for x in col)\n",
    "            if zero_cnt > m - zero_cnt:\n",
    "                diff += (zero_cnt * 2 - m) * (1 << j)\n",
    "            j -= 1\n",
    "\n",
    "        ans += diff\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        cnt = [0] * n\n",
    "        for i in range(m):\n",
    "            t = 1-grid[i][0]\n",
    "            for j in range(n):\n",
    "                grid[i][j] ^= t\n",
    "                if grid[i][j]: cnt[j] += 1\n",
    "        # for l in grid: print(l)\n",
    "        # print(cnt)\n",
    "        ans = 0\n",
    "        for c in cnt: ans = (ans<<1) + max(c,m-c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # 步骤1：确保每一行的最左侧位都是1\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j] = 1 - grid[i][j]  # 翻转行\n",
    "        \n",
    "        # 步骤2：尽量确保每一列的1的数量大于0的数量\n",
    "        for j in range(1, n):\n",
    "            ones = sum(grid[i][j] for i in range(m))\n",
    "            if ones <= m // 2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j] = 1 - grid[i][j]  # 翻转列\n",
    "        \n",
    "        # 计算最终得分\n",
    "        score = 0\n",
    "        for i in range(m):\n",
    "            score += int(''.join(map(str, grid[i])), 2)\n",
    "        \n",
    "        return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            if not grid[i][0]:\n",
    "                for j in range(len(grid[i])):\n",
    "                    grid[i][j] = grid[i][j] ^ 1\n",
    "        ans = 0\n",
    "        tgt = len(grid)\n",
    "        lll = len(grid[0])\n",
    "        for j in range(len(grid[0])):\n",
    "            tmp = 0\n",
    "            for i in range(0,len(grid)):\n",
    "                if grid[i][j]:\n",
    "                    tmp += 1\n",
    "            ans = ans + (max(tmp,tgt - tmp) << (lll - j - 1) )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        for j in range(n):\n",
    "            if sum([grid[k][j] for k in range(m)])<=len(grid)//2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        for i in range(m):\n",
    "            t=1\n",
    "            for j in range(n-1,-1,-1):\n",
    "                result+=grid[i][j]*t\n",
    "                t*=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Greedy. Time O(mn) Space O(m)\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # examine rows first. if starts with 0, flip the row will always make it bigger\n",
    "        toggleRow = [False for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                toggleRow[i] = True\n",
    "        res = 0\n",
    "        # examine cols except for col 0. if there are more 0s than 1s, flip the col\n",
    "        # this is equivalant to using the max(zero, one) as the number of 1s\n",
    "        for j in range(n):\n",
    "            zero, one = 0, 0\n",
    "            for i in range(m):\n",
    "                if (grid[i][j] == 1 and toggleRow[i]) or \\\n",
    "                   (grid[i][j] == 0 and not toggleRow[i]):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    one += 1\n",
    "            res += max(zero, one) * 2 ** (n - j - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = m*(1 << (n-1))\n",
    "        for j in range(1,n):\n",
    "            # 统计一列的1的个数\n",
    "            cnt1 = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0]:\n",
    "                    cnt1 += grid[i][j]\n",
    "                else:\n",
    "                    cnt1 += 1 - grid[i][j]\n",
    "            k = max(cnt1,m-cnt1)\n",
    "            ans += k*(1 <<(n-j-1))\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = m * (1 << (n - 1))\n",
    "        for j in range(1, n):\n",
    "            nOnes = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0] == 1:\n",
    "                    nOnes += grid[i][j]\n",
    "                else:\n",
    "                    nOnes += (1 - grid[i][j])\n",
    "            k = max(nOnes, m - nOnes)\n",
    "            ans += k * (1 << (n - j - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        # 翻转第一列为0的行\n",
    "        for i in grid:\n",
    "            if i[0] == 0:\n",
    "                for j in range(n):\n",
    "                    i[j] = 0 if i[j] == 1 else 1\n",
    "        # 翻转每列\n",
    "        for i in range(1, n):\n",
    "            nums = [grid[j][i] for j in range(m)]\n",
    "            if nums.count(1) > m // 2: \n",
    "                continue\n",
    "            else:\n",
    "                for j in range(m):\n",
    "                    grid[j][i] = 0 if grid[j][i] == 1 else 1 \n",
    "        # 求和\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1: res += 2 ** (n - j - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        for i in range(len(grid)):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(len(grid[0])):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        for j in range(len(grid[0])):\n",
    "            if sum([grid[k][j] for k in range(len(grid))])<=len(grid)//2:\n",
    "                for i in range(len(grid)):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        for i in range(len(grid)):\n",
    "            t=1\n",
    "            for j in range(len(grid[0])-1,-1,-1):\n",
    "                result+=grid[i][j]*t\n",
    "                t*=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        # 首先考虑行的翻转，如果最高位是零，那就翻转，因为最高位的权重最大\n",
    "        # 然后列翻转，这一列如果0比1多，那就翻转这一列\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j] = 1 - grid[i][j]\n",
    "        \n",
    "        for j in range(n):\n",
    "            one_num = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    one_num += 1\n",
    "            if one_num<m/2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j] = 1 - grid[i][j]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    res += 2**(n-j-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = m*(1 << (n-1))\n",
    "        for j in range(1,n):\n",
    "            one = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0] == 1:\n",
    "                    one += grid[i][j]\n",
    "                else:\n",
    "                    one += 1-grid[i][j]\n",
    "            k = max(m-one,one)\n",
    "            ans += k*(1 << (n-j-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for row in grid:\n",
    "            if row[0] == 0:\n",
    "                for j in range(n):\n",
    "                    row[j] ^= 1\n",
    "        ans = m*2**(n - 1)\n",
    "       \n",
    "        for j,col in enumerate(list(zip(*grid))):\n",
    "            if j == 0:\n",
    "                continue\n",
    "            ans += Counter(col).most_common(1)[0][1] * (2**(n - j - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def flipRow(r):\n",
    "            for c in range(C):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def flipCol(c):\n",
    "            for r in range(R):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def checkRow(nums):\n",
    "            return int(''.join([str(n) for n in nums]), 2)\n",
    "\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        for r in range(R):\n",
    "            if grid[r][0] == 0:\n",
    "                flipRow(r)\n",
    "        for c in range(1, C):\n",
    "            if sum(grid[r][c] for r in range(R)) * 2 < R:\n",
    "                flipCol(c)\n",
    "        return sum(checkRow(row) for row in grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid):\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ret = m * (1 << (n - 1))\n",
    "\n",
    "        for j in range(1, n):\n",
    "            nOnes = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0] == 1:\n",
    "                    nOnes += grid[i][j]\n",
    "                else:\n",
    "                    nOnes += 1 - grid[i][j]\n",
    "            \n",
    "            k = max(nOnes, m - nOnes)\n",
    "            ret += k * (1 << (n - j - 1))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [0 for _ in range(m)]\n",
    "        ans = m * (1 << (n - 1))\n",
    "        for r in range(m):\n",
    "            if grid[r][0] == 0: rs[r] += 1\n",
    "        for c in range(1, n):\n",
    "            cnt = 0\n",
    "            for r in range(m):\n",
    "                if (grid[r][c] + rs[r]) % 2 == 1: cnt += 1\n",
    "            if m - cnt > cnt: cnt = m - cnt\n",
    "            ans += cnt * (1 << (n - c - 1))\n",
    "        tmp = m * (1 << (n - 1))\n",
    "        rs = [0 for _ in range(m)]\n",
    "        for r in range(m):\n",
    "            if grid[r][0] == 1: rs[r] += 1\n",
    "        for c in range(1, n):\n",
    "            cnt = 0\n",
    "            for r in range(m):\n",
    "                if (grid[r][c] + rs[r]) % 2 == 1: cnt += 1\n",
    "            if m - cnt > cnt: cnt = m - cnt\n",
    "            tmp += cnt * (1 << (n - c - 1))\n",
    "        return max(tmp, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def reverse_row(i):\n",
    "            for j in range(n):\n",
    "                grid[i][j] ^= 1\n",
    "\n",
    "        def reverse_col(j):\n",
    "            for i in range(m):\n",
    "                grid[i][j] ^= 1\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            if not grid[i][0]:\n",
    "                reverse_row(i)\n",
    "        for j in range(n):\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                cnt += grid[i][j]\n",
    "            if cnt < m / 2:\n",
    "                reverse_col(j)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    continue\n",
    "                ans += 1 << (n - j - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(n):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(m):\n",
    "                    grid[i][j] ^= 1\n",
    "\n",
    "        for j in range(1, m):\n",
    "            ones = 0\n",
    "            for i in range(n):\n",
    "                ones += grid[i][j]\n",
    "            if ones < int(n / 2 + 0.6):\n",
    "                for i in range(n):\n",
    "                    grid[i][j] ^= 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans += grid[i][j] * 2 ** (m - j - 1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def flipRow(r):\n",
    "            for c in range(C):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def flipCol(c):\n",
    "            for r in range(R):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def checkBinary(nums):\n",
    "            return int(''.join([str(n) for n in nums]), 2)\n",
    "\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        for r in range(R):\n",
    "            if grid[r][0] == 0:\n",
    "                flipRow(r)\n",
    "        for c in range(1, C):\n",
    "            if sum(grid[r][c] for r in range(R)) * 2 < R:\n",
    "                flipCol(c)\n",
    "        return sum(checkBinary(row) for row in grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = (1 << (n - 1)) * m\n",
    "        shift = [1 - grid[i][0] for i in range(m)]\n",
    "        for j in range(1, n):\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                if (shift[i] + grid[i][j]) % 2:\n",
    "                    cnt += 1\n",
    "            if cnt < m / 2:\n",
    "                cnt = m - cnt\n",
    "                for i in range(m):  shift[i] += 1\n",
    "            ans += (1 << (n - j - 1)) * cnt\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        # 贪心策略：对于每一行，如果首元素是0，则进行移动；对于每一列，如果0的数目大于1的数目，则移动\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for i in range(n):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(m):\n",
    "                    grid[i][j] = 1 if grid[i][j]==0 else 0\n",
    "\n",
    "        trans = []\n",
    "        for i in range(m):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                cnt+=grid[j][i]\n",
    "            if cnt<(n+1)//2:\n",
    "                trans.append(i)\n",
    "\n",
    "        for item in trans:\n",
    "            for k in range(n):\n",
    "                    grid[k][item] = 1 if grid[k][item]==0 else 0\n",
    "\n",
    "        res = 0\n",
    "        for item in grid:\n",
    "            val = 0\n",
    "            for j in range(m):\n",
    "                val = val*2+item[j]\n",
    "            res+=val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = (1 << (n - 1)) * m\n",
    "        shift = [1 - grid[i][0] for i in range(m)]\n",
    "        for j in range(1, n):\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                if (shift[i] + grid[i][j]) % 2:\n",
    "                    cnt += 1\n",
    "            if cnt < m / 2:\n",
    "                cnt = m - cnt\n",
    "                for i in range(m):  shift[i] += 1\n",
    "            ans += (1 << (n - j - 1)) * cnt\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        res = n\n",
    "\n",
    "        for i in range(1, m):\n",
    "            res <<= 1\n",
    "            s = sum([grid[j][i] ^ grid[j][0] for j in range(n)])\n",
    "            res += max(s, n - s)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=dict()\n",
    "        for i in range(m):\n",
    "            grid[i]=sum(2**(n-j-1) for j in range(n) if grid[i][j])\n",
    "        for i in range(m):\n",
    "            if grid[i]&(1<<(n-1)): continue\n",
    "            grid[i]=~grid[i]\n",
    "        res[0]=m\n",
    "        for j in range(1,n):\n",
    "            cnt=0\n",
    "            for num in grid:\n",
    "                if num&(1<<(n-j-1)): cnt+=1\n",
    "            if m-cnt>cnt:\n",
    "                cnt=m-cnt\n",
    "            res[j]=cnt\n",
    "        ans=0\n",
    "        for x in res:\n",
    "            ans+=2**(n-x-1)*res[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        a = [m]+[0]*(n-1)\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                x = 0\n",
    "            else:\n",
    "                x = 1\n",
    "            for j in range(1,n):\n",
    "                if (x and grid[i][j] == 1) or (not x and grid[i][j] == 0):\n",
    "                    a[j] += 1\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            ans += 2**(n-j-1)*max(a[j],m-a[j])\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def fanzhuan(nums,n):\n",
    "            for i in range(n):\n",
    "                nums[i]=0 if nums[i]==1 else 1\n",
    "        \n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                fanzhuan(grid[i],n)\n",
    "        \n",
    "        ans=2**n *m\n",
    "        for j in range(1,n):\n",
    "            tmp=sum([grid[i][j] for i in range(m)])\n",
    "            ans+=2**(n-j)*max(tmp,m-tmp)\n",
    "\n",
    "        return ans//2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      ans = 0\n",
    "      for i in range(m):\n",
    "        if grid[i][0] == 0:\n",
    "          for j in range(n):\n",
    "            grid[i][j] ^= 1\n",
    "      for j in range(n):\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "          cnt += grid[i][j]\n",
    "        ans += max(m - cnt, cnt) * (1 << (n - j - 1))\n",
    "      return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for r in range(m):\n",
    "            if grid[r][0] == 0:\n",
    "                for c in range(n):\n",
    "                    grid[r][c] = 1 - grid[r][c]\n",
    "        \n",
    "        t = 2 ** (n - 1)\n",
    "        a = t * m \n",
    "        for c in range(1, n):\n",
    "            t //= 2\n",
    "            z = sum([x[c] for x in grid])\n",
    "            z = max(z, m - z)\n",
    "            a += t * z\n",
    "        \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        temp=2**(n-1)\n",
    "        for j in range(n):\n",
    "            Sum=sum([grid[k][j] for k in range(m)])\n",
    "            if Sum<=m//2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "                Sum=m-Sum\n",
    "            result+=Sum*temp\n",
    "            temp//=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=dict()\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==1:continue\n",
    "            for j in range(n):\n",
    "                grid[i][j]^=1\n",
    "        res[0]=m\n",
    "        for j in range(1,n):\n",
    "            cnt=0\n",
    "            for k in range(m):\n",
    "                cnt+=grid[k][j]==1\n",
    "            if m-cnt>cnt:\n",
    "                cnt=m-cnt\n",
    "            res[j]=cnt\n",
    "        return sum(2**(n-i-1)*res[i] for i in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        #先按行翻转，翻转第一个值为0的行\n",
    "        #再按列翻转，翻转0多于1的列\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 0:\n",
    "                        grid[i][j] = 1\n",
    "                    else:\n",
    "                        grid[i][j] = 0\n",
    "        for i in range(1,n):\n",
    "            count_0 = 0\n",
    "            for j in range(m):\n",
    "                if grid[j][i] == 0:\n",
    "                    count_0 += 1\n",
    "            if count_0 > m/2:\n",
    "                for k in range(m):\n",
    "                    if grid[k][i] == 0:\n",
    "                        grid[k][i] = 1\n",
    "                    else:\n",
    "                        grid[k][i] = 0\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    res += 2 **(n-j-1)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Greedy. Time O(mn) Space O(m)\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # examine rows first. if starts with 0, flip the row will always make it bigger\n",
    "        toggleRow = [False for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                toggleRow[i] = True\n",
    "        res = 0\n",
    "        # examine cols next. if there are more 0s than 1s, flip the col\n",
    "        # this is equivalant to using the max(zero, one) as the number of 1s\n",
    "        for j in range(n):\n",
    "            zero, one = 0, 0\n",
    "            for i in range(m):\n",
    "                if (grid[i][j] == 1 and toggleRow[i]) or \\\n",
    "                   (grid[i][j] == 0 and not toggleRow[i]):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    one += 1\n",
    "            res += max(zero, one) * 2 ** (n - j - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(0,m):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(0,n):\n",
    "                    grid[i][j] = 1 - grid[i][j]\n",
    "        res = 0\n",
    "        for j in range(0,n):\n",
    "            k = 0\n",
    "            for i in range(0,m):\n",
    "                k += grid[i][j]\n",
    "            k = max(k,m-k)\n",
    "            res += k * (2**(n-1-j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "        result=0\n",
    "        temp=2**(n-1)\n",
    "        for j in range(n):\n",
    "            Sum=sum([grid[k][j] for k in range(m)])\n",
    "            if Sum<=m//2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j]=1-grid[i][j]\n",
    "                Sum=m-Sum\n",
    "            result+=Sum*temp\n",
    "            temp//=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # 第一列全翻转成1\n",
    "        for row in grid:\n",
    "            if row[0] == 0:\n",
    "                for j in range(n):\n",
    "                    row[j] ^= 1\n",
    "        ans = m*2**(n - 1)\n",
    "       \n",
    "        # 从第二列开始计算贡献度，0和1的最大值就是翻转后1的数量\n",
    "        for j,col in enumerate(list(zip(*grid))):\n",
    "            if j == 0:\n",
    "                continue\n",
    "            ans += Counter(col).most_common(1)[0][1] * 2**(n - j - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        la = len(grid)\n",
    "        lc = len(grid[0])\n",
    "        cnt_col = [0] * lc\n",
    "        for i in range(la):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(lc):\n",
    "                    grid[i][j] ^= 1\n",
    "                    cnt_col[j] += grid[i][j]\n",
    "            else:\n",
    "                for j in range(lc):\n",
    "                    cnt_col[j] += grid[i][j]\n",
    "        for i in range(lc):\n",
    "            if cnt_col[i] <= la // 2:\n",
    "                for j in range(la):\n",
    "                    grid[j][i] ^= 1\n",
    "        #print(cnt_col, grid)\n",
    "        ans = 0\n",
    "        for i in range(la):\n",
    "            for j in range(lc):\n",
    "                ans += grid[i][j] * (2 ** (lc - 1 - j))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def flipRow(r):\n",
    "            for c in range(C):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def flipCol(c):\n",
    "            for r in range(R):\n",
    "                grid[r][c] = 1 - grid[r][c]\n",
    "\n",
    "        def checkBinary(nums):\n",
    "            return int(''.join([str(n) for n in nums]), 2)\n",
    "\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        for r in range(R):\n",
    "            if grid[r][0] == 0:\n",
    "                flipRow(r)\n",
    "        for c in range(1, C):\n",
    "            if sum(grid[r][c] for r in range(R)) * 2 < R:\n",
    "                flipCol(c)\n",
    "        print(grid)\n",
    "        return sum(checkBinary(row) for row in grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=dict()\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==1:continue\n",
    "            for j in range(n):\n",
    "                grid[i][j]^=1\n",
    "        res[0]=m\n",
    "        for j in range(1,n):\n",
    "            cnt=0\n",
    "            for k in range(m):\n",
    "                cnt+=grid[k][j]==1\n",
    "            if m-cnt>cnt:\n",
    "                cnt=m-cnt\n",
    "            res[j]=cnt\n",
    "        return sum(2**(n-i-1)*res[i] for i in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = m * (1 << (n-1))\n",
    "\n",
    "        for j in range(1, n):\n",
    "            cnt_one = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][0] == 1:\n",
    "                    cnt_one += grid[i][j]\n",
    "                else:\n",
    "                    cnt_one += 1 - grid[i][j]\n",
    "            k = max(cnt_one, m - cnt_one)\n",
    "            ans +=  k * (1 << (n - j - 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\r\n",
    "        R,C=len(grid),len(grid[0])\r\n",
    "        # row_flip=[False]*R\r\n",
    "        # col_flip=[False]*C\r\n",
    "        for r in range(R):\r\n",
    "            if grid[r][0]==0:\r\n",
    "                for c in range(C):\r\n",
    "                    grid[r][c]=1-grid[r][c]\r\n",
    "        ret=0\r\n",
    "        ret+=(1<<(C-1))*R\r\n",
    "        for c in range(1,C):\r\n",
    "            one_cnt=0\r\n",
    "            for r in range(R):               \r\n",
    "                if grid[r][c]==1:\r\n",
    "                    one_cnt+=1\r\n",
    "            ret+=(1<<(C-1-c))*max(one_cnt,R-one_cnt)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=dict()\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==1:continue\n",
    "            for j in range(n):\n",
    "                grid[i][j]^=1\n",
    "        res[0]=m\n",
    "        for j in range(1,n):\n",
    "            cnt=0\n",
    "            for k in range(m):\n",
    "                cnt+=grid[k][j]==1\n",
    "            if m-cnt>cnt:\n",
    "                cnt=m-cnt\n",
    "            res[j]=cnt\n",
    "        return sum(2**(n-i-1)*res[i] for i in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==0:\n",
    "                        grid[i][j]=1\n",
    "                    else:\n",
    "                        grid[i][j]=0\n",
    "        #print(grid)\n",
    "        for i in range(1, n):\n",
    "            one_count=0\n",
    "            zero_count=0\n",
    "            for j in range(m):\n",
    "                if grid[j][i]==0:\n",
    "                    zero_count+=1\n",
    "                else:\n",
    "                    one_count+=1\n",
    "            if zero_count>one_count:\n",
    "                for j in range(m):\n",
    "                    if grid[j][i]==0:\n",
    "                        grid[j][i]=1\n",
    "                    else:\n",
    "                        grid[j][i]=0\n",
    "        #print(grid)\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            temp=''\n",
    "            for j in range(n):\n",
    "                temp+=str(grid[i][j])\n",
    "            res+=int(temp,2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        # 第一步一定是让最高位变为1\n",
    "        # 第二步考虑较低位上1多于0即可\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        total_sum = m*2**(n-1)\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 1:\n",
    "                continue\n",
    "            for j in range(1,n):\n",
    "                grid[i][j] ^= 1\n",
    "        for j in range(1,n):\n",
    "            # 统计0和1的个数\n",
    "            ones_count = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    ones_count += 1\n",
    "            max_ones = max(ones_count,m - ones_count)\n",
    "            total_sum += 2**(n-1-j)*max_ones\n",
    "        return total_sum\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, A: List[List[int]]) -> int:\n",
    "        n_row, n_col = len(A), len(A[0])\n",
    "        ans = 0  # 最终结果\n",
    "        for c in range(n_col):\n",
    "            cur_sum = 0  # 计数每一列中1的个数\n",
    "            for r in range(n_row):\n",
    "                cur_sum += A[r][c]^A[r][0]^1 # 累加选择性行反转之后的值\n",
    "            ans += max(cur_sum, n_row-cur_sum) * pow(2, n_col-c-1)  # 当前值和列反转后的值取较大者*位权\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, A: List[List[int]]) -> int:\n",
    "        n, m = len(A), len(A[0])\n",
    "        res = n\n",
    "\n",
    "        for i in range(1, m):\n",
    "            res <<= 1\n",
    "            s = sum([A[j][i] ^ A[j][0] for j in range(n)])\n",
    "            res += max(s, n - s)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            if grid[i][0]==0:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==0:\n",
    "                        grid[i][j]=1\n",
    "                    else:\n",
    "                        grid[i][j]=0\n",
    "        print(grid)\n",
    "        for j in range(n):\n",
    "            count0=0\n",
    "            count1=0\n",
    "            for i in range(m):\n",
    "                if grid[i][j]==0:\n",
    "                    count0+=1\n",
    "                if grid[i][j]==1:\n",
    "                    count1+=1\n",
    "            if count0>count1:\n",
    "                for i in range(m):\n",
    "                    if grid[i][j]==0:\n",
    "                        grid[i][j]=1\n",
    "                    else:\n",
    "                        grid[i][j]=0\n",
    "        ans=0\n",
    "       # print(grid)\n",
    "        for i in range(m):\n",
    "            tmp=[str(x) for x in grid[i]]\n",
    "            s=\"\".join(tmp)\n",
    "            ans+=int(s,2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                for j in range(n):\n",
    "                    grid[i][j] = 1 - grid[i][j]\n",
    "        \n",
    "        for j in range(n):\n",
    "            one_num = 0\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    one_num += 1\n",
    "            if one_num<m/2:\n",
    "                for i in range(m):\n",
    "                    grid[i][j] = 1 - grid[i][j]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    res += 2**(n-j-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        a = [m]+[0]*(n-1)\n",
    "        for i in range(m):\n",
    "            if grid[i][0] == 0:\n",
    "                x = 0\n",
    "            else:\n",
    "                x = 1\n",
    "            for j in range(1,n):\n",
    "                if (x and grid[i][j] == 1) or (not x and grid[i][j] == 0):\n",
    "                    a[j] += 1\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            ans += 2**(n-j-1)*max(a[j],m-a[j])\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixScore(self, grid: List[List[int]]) -> int:\n",
    "        def getline(grid, col):\n",
    "            return [grid[i][col] for i in range(len(grid))]\n",
    "        def reverserow(grid, row):\n",
    "            for j in range(len(grid[0])):\n",
    "                grid[row][j] = 0 if grid[row][j] == 1 else 1\n",
    "        def reversecol(grid, col):\n",
    "            for i in range(len(grid)):\n",
    "                grid[i][col] = 0 if grid[i][col] == 1 else 1\n",
    "        col0 = getline(grid, 0)\n",
    "        for i in range(len(col0)):\n",
    "            if col0[i] == 0:\n",
    "                reverserow(grid, i)\n",
    "        col = 1\n",
    "        while col < len(grid[0]):\n",
    "            cols = getline(grid, col)\n",
    "            if cols.count(0) > cols.count(1):\n",
    "                reversecol(grid, col)\n",
    "            col += 1\n",
    "        ret = 0\n",
    "        #print(grid)\n",
    "        for nums in grid:\n",
    "            res = 1\n",
    "            for num in nums[1: len(nums)]:\n",
    "                #print(res)\n",
    "                res = (res << 1) + num\n",
    "                #print(res)\n",
    "            ret += res\n",
    "        return ret\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
